package MultiSourceShortestPath;

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfEnclaves {
    // 单源BFS
    // 把连接边缘 `1` 的边缘块修改成 -1, 然后再去遍历里面的 `1` 的数量
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};

    int m; // 对应 x 坐标
    int n; // 对应 y 坐标
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        // 1.处理边缘连通块(首行和尾行)
        for(int y = 0; y < n; y++) {
            if(grid[0][y] == 1) {
                bfs(grid, 0, y);
            }
            if(grid[m - 1][y] == 1) {
                bfs(grid, m-1, y);
            }
        }

        // 首列和尾列
        for(int x = 0; x < m; x++) {
            if(grid[x][0] == 1) {
                bfs(grid, x, 0);
            }
            if(grid[x][n-1] == 1) {
                bfs(grid, x, n-1);
            }
        }

        // 遍历源数组, 数出 1 的个数
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    ret++;
                }
            }
        }
        return ret;
    }

    // 把 `1` 变成 -1
    public void bfs(int[][] grid, int OOx, int OOy) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{OOx, OOy});
        grid[OOx][OOy] = -1;

        while(!queue.isEmpty()) {
            // 取出原点
            int[] point = queue.poll();
            // 分解点坐标
            int Ox = point[0];
            int Oy = point[1];

            // 遍历下一层节点
            for(int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                    queue.offer(new int[]{x, y});
                    grid[x][y] = -1;
                }
            }
        }
    }


    public int numEnclaves1(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();

        // 1.处理边缘连通块(首行和尾行)
        for(int y = 0; y < n; y++) {
            if(grid[0][y] == 1) {
                grid[0][y] = -1;
                queue.offer(new int[]{0, y});
            }
            if(grid[m - 1][y] == 1) {
                grid[m - 1][y] = -1;
                queue.offer(new int[]{m-1, y});
            }
        }

        // 首列和尾列
        for(int x = 0; x < m; x++) {
            if(grid[x][0] == 1) {
                grid[x][0] = -1;
                queue.offer(new int[]{x, 0});
            }
            if(grid[x][n-1] == 1) {
                grid[x][n-1] = -1;
                queue.offer(new int[]{x, n-1});
            }
        }

        // 把 `1` 变成 -1
        while(!queue.isEmpty()) {
            // 取出原点
            int[] point = queue.poll();
            // 分解点坐标
            int Ox = point[0];
            int Oy = point[1];

            // 遍历下一层节点
            for(int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                    queue.offer(new int[]{x, y});
                    grid[x][y] = -1;
                }
            }
        }

        // 遍历源数组, 数出 1 的个数
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    ret++;
                }
            }
        }
        return ret;
    }
}
